package com.algo.Jaya;

import java.util.*;

/**
 * @Author: guoxing
 * @Email: gx_study2022@163.com
 * @Description: https://blog.csdn.net/qq_37853160/article/details/127273019
 * @Date: 2024/6/24 22:29
 * @ClassName: JayaAlgorithm
 **/
public class JayaAlgorithm {
    private int popNum;
    private int iterateNum;
    private RawData rawData;

    public Individual getResult() {
        Population population = init(); // 初始化种群

        for (int i = 0; i < this.iterateNum; i++) { // 算法迭代
            // 对种群进行Pareto快速非支配排序
            LinkedList<List<Individual>> lists = fastNonDominatedSort(population);
            // 通过拥挤距离获取种群中的最优与最劣个体
            Individual[] bestAndWorst = calCrowding(lists);
            population.setBest1(bestAndWorst[0]);
            population.setWorst1(bestAndWorst[1]);
            // 种群进化
            population = evolvePopulaiton(population);
        }
        // 对种群进行非支配排序、计算拥挤距离，以获得最终结果
        LinkedList<List<Individual>> lists = fastNonDominatedSort(population);
        Individual[] bestAndWorst = calCrowding(lists);
        return bestAndWorst[0];
    }

    public JayaAlgorithm(int popNum, int iterateNum, RawData rawData) {
        this.popNum = popNum;
        this.iterateNum = iterateNum;
        this.rawData = rawData;
    }

//    public JayaAlgorithm(RawData data,JayaConfig config){
//
//    }

    public Population init() {
        return new Population(this.rawData, this.popNum);
    }

    /**
     * 种群进化
     *
     * @return
     */
    private Population evolvePopulaiton(Population population) {
        Population newPopulation = new Population(popNum);
        Individual best = population.getBest();
        Individual worst = population.getWorst();
        newPopulation.setIndividual(0, best);
        for (int i = 1; i < population.size(); i++) {
            Individual individual = population.getIndividual(i);
            Individual newIndividual = evolveIndividual(individual, best, worst);
            if (newIndividual.dominate(individual)) {
                newPopulation.setIndividual(i, newIndividual);
            } else {
                newPopulation.setIndividual(i, individual);
            }
        }
        return newPopulation;
    }

    /**
     * 对个体进行进化
     *
     * @param individual 当前个体
     * @param best       最优个体
     * @param worst      最劣个体
     * @return 进化后的个体
     */
    private Individual evolveIndividual(Individual individual, Individual best, Individual worst) {
        // 机器编码部分
        int[] machine = new int[individual.getCodeLength()];
        for (int i = 0; i < machine.length; i++) {
            if (individual.getGene(0, i) == worst.getGene(0, i)) {
                machine[i] = best.getGene(0, i);
                continue;
            }
            machine[i] = individual.getGene(0, i);
        }
        // 工序编码部分
        int[] process = new int[individual.getCodeLength()];
        for (int i = 0; i < process.length; i++) {
            if (individual.getGene(1, i) != worst.getGene(1, i)) {
                process[i] = individual.getGene(1, i);
            }
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int p : process) {
            if (p != 0) {
                map.put(p, map.getOrDefault(p, 0) + 1);
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < best.getCodeLength(); j++) {
            int gene = best.getGene(1, j);
            if (map.getOrDefault(gene, 0) == 0) {
                list.add(gene);
            } else {
                map.put(gene, map.get(gene) - 1);
            }
        }
        int index = 0;
        if (list.size() != 0) {
            for (int i = 0; i < process.length; i++) {
                if (process[i] == 0) {
                    process[i] = list.get(index++);
                }
            }
        }
        return new Individual(machine, process, individual.getRawData());
    }

    /**
     * 快速非支配排序
     *
     * @param pop 需要进行排序的种群
     * @return 使用LinkedList方便获取最优层和最劣层
     */
    private LinkedList<List<Individual>> fastNonDominatedSort(Population pop) {
        Individual[] individuals = pop.getIndividuals();
        Map<Individual, Integer> isDominateNum = new HashMap<>();
        Map<Individual, List<Individual>> dominate = new HashMap<>();

        for (int i = 0; i < individuals.length; i++) {
            int n = 0;
            List<Individual> list = new ArrayList<>();
            for (int j = 0; j < individuals.length; j++) {
                if (i == j) {
                    continue;
                }
                if (individuals[i].dominate(individuals[j])) {
                    list.add(individuals[j]);
                }
                if (individuals[j].dominate(individuals[i])) {
                    n++;
                }
            }

            isDominateNum.put(individuals[i], n);
            dominate.put(individuals[i], list);
        }

        LinkedList<List<Individual>> res = new LinkedList<>();


        // 此处容易陷入死循环
        while (isDominateNum.size() != 0) {
            List<Individual> list = new ArrayList<>();
            for (Map.Entry<Individual, Integer> individualIntegerEntry : isDominateNum.entrySet()) {
                if (individualIntegerEntry.getValue() == 0) {
                    list.add(individualIntegerEntry.getKey());
                }
            }

            res.add(list);
            if (list.size() == 0) {
                for (Map.Entry<Individual, Integer> individualIntegerEntry : isDominateNum.entrySet()) {
                    list.add(individualIntegerEntry.getKey());
                }
                break;
            }

            for (Individual individual : list) {
                isDominateNum.remove(individual);
                for (Individual individual1 : dominate.get(individual)) {
                    try {
                        // isDominateNum.get(individual1) - 1可能造成空指针
                        isDominateNum.put(individual1, isDominateNum.get(individual1) - 1);
                    } catch (NullPointerException e) {
                        e.printStackTrace();
                        e.getMessage();
                    }

                }
            }
        }
        return res;
    }

    /**
     * 计算拥距离
     *
     * @param fastSort 经过快速非支配排序得到的结果
     * @return 个体数组，第一个表示最优个体，第二个表示最劣个体
     */
    private Individual[] calCrowding(LinkedList<List<Individual>> fastSort) {
        Individual[] res = new Individual[2];
        List<Individual> first = fastSort.getFirst(); List<Individual> last = fastSort.getLast();
        Random rnd = new Random();
        if (first.size() < 3) {
            res[0] = first.get(rnd.nextInt(first.size()));
        } else {
            Map<Individual, Integer> map = new HashMap<>();
            Individual[] individuals = first.toArray(new Individual[first.size()]);

            Arrays.sort(individuals, (o1, o2) -> o1.getFinishTime() - o2.getFinishTime());

            map.put(individuals[0], Integer.MAX_VALUE / 2);
            map.put(individuals[individuals.length - 1], Integer.MAX_VALUE / 2);

            for (int i = 1; i < individuals.length - 1; i++) {
                int num = Math.abs(individuals[i].getFinishTime() - individuals[i + 1].getFinishTime()) +
                        Math.abs(individuals[i].getFinishTime() - individuals[i - 1].getFinishTime());
                map.put(individuals[i], num);
            }

            Arrays.sort(individuals, (o1, o2) -> o1.getFreeTime() - o2.getFreeTime());

            map.put(individuals[0], map.get(individuals[0]) + Integer.MAX_VALUE / 2);
            map.put(individuals[individuals.length - 1], map.get(individuals[individuals.length - 1]) + Integer.MAX_VALUE / 2);

            for (int i = 1; i < individuals.length - 1; i++) {
                int num = Math.abs(individuals[i].getFreeTime() - individuals[i + 1].getFreeTime()) +
                        Math.abs(individuals[i].getFreeTime() - individuals[i - 1].getFreeTime());
                map.put(individuals[i], map.get(individuals[i]) + num);
            }

            int max = -1;
            Individual best = null;
            for (Map.Entry<Individual, Integer> individualIntegerEntry : map.entrySet()) {
                if (individualIntegerEntry.getValue() > max) {
                    max = individualIntegerEntry.getValue();
                    best = individualIntegerEntry.getKey();
                }
            }
            res[0] = best;
        }

        if (last.size() < 3) {
            res[1] = last.get(rnd.nextInt(last.size()));
        } else {
            Map<Individual, Integer> map = new HashMap<>();
            Individual[] individuals = last.toArray(new Individual[last.size()]);

            Arrays.sort(individuals, (o1, o2) -> o1.getFinishTime() - o2.getFinishTime());

            map.put(individuals[0], Integer.MAX_VALUE / 2);
            map.put(individuals[individuals.length - 1], Integer.MAX_VALUE / 2);

            for (int i = 1; i < individuals.length - 1; i++) {
                int num = Math.abs(individuals[i].getFinishTime() - individuals[i + 1].getFinishTime()) +
                        Math.abs(individuals[i].getFinishTime() - individuals[i - 1].getFinishTime());
                map.put(individuals[i], num);
            }

            Arrays.sort(individuals, (o1, o2) -> o1.getFreeTime() - o2.getFreeTime());

            map.put(individuals[0], map.get(individuals[0]) + Integer.MAX_VALUE / 2);
            map.put(individuals[individuals.length - 1], map.get(individuals[individuals.length - 1]) + Integer.MAX_VALUE / 2);

            for (int i = 1; i < individuals.length - 1; i++) {
                int num = Math.abs(individuals[i].getFreeTime() - individuals[i + 1].getFreeTime()) +
                        Math.abs(individuals[i].getFreeTime() - individuals[i - 1].getFreeTime());
                map.put(individuals[i], map.get(individuals[i]) + num);
            }

            int min = Integer.MAX_VALUE;
            Individual worst = null;
            for (Map.Entry<Individual, Integer> individualIntegerEntry : map.entrySet()) {
                if (individualIntegerEntry.getValue() < min) {
                    min = individualIntegerEntry.getValue();
                    worst = individualIntegerEntry.getKey();
                }
            }
            res[1] = worst;
        }
        return res;
    }

    LinkedList<List<Individual>> nonDominateSort(Population population){
        LinkedList<List<Individual>> result = new LinkedList<>(); // 最终结果
        while(population.size()>1){
            List<Individual> list = new ArrayList<Individual>(); // 一个Pareto前沿
            out:for(int i=0;i<population.size();i++){
                Individual i1 = population.getIndividual(i);
                for(int j=0;j<population.size();j++){
                    Individual i2 = population.getIndividual(j);
                    if(i1.equals(i2)) {
                        continue;
                    }
                    if(i2.dominate(i1)) {
                        continue out;
                    }
                }
                // 如果种群中其它所有个体都无法支配i1，则将i1添加至当前Pareto前沿
                list.add(i1);
            }
            result.add(list); // 将当前Pareto前沿添加至结果集中
            // TODO: 2024/6/24  此处注释了要修改 
//            population.remove(list); // 从population中移除存在于list中的individual
        }
        // ...
        return result;
    }
}

